A large number of protocols pertaining to the Internet Protocol suite have employed packet encapsulation (alternatively, packet tunneling). In IPv6 (Internet Protocol version 6), this packet encapsulation is principally defined in the following Non-Patent Document 1.
For example, Virtual Private Network (VPN) uses a tunneling technique to interconnect two or more networks existing at different locations for the formation of a large-scale private network.
In addition, Mobility Support in Mobile IPv6 (MIPv6) uses tunneling between mobile nodes and home agents to allow a mobile node to be always reachable at its home address.
Still additionally, Network Mobility Support (NEMO) in IPv6 specifies that a mobile router should establish tunnel with its home agent to allow a whole network to roam the Internet while still reachable at the mobile network prefix.
IPv6 tunneling is the encapsulation of an inner IPv6 packet as the payload of an outer IPv6 packet. The inner packet is sometimes referred to as payload packet, while the outer packet is sometimes referred to as tunnel packet.
The tunneling involves two entities: a tunnel entry node and a tunnel exit node. In this specification, the tunnel entry node is sometimes expressed as a tunnel entry point or TEP while the tunnel exit node is sometimes expressed as a tunnel exit point.
The tunnel entry node encapsulates a payload packet into or with a tunnel packet having an address of the tunnel entry node as a source address and having an address of the tunnel exit node as a destination address. When the tunnel packet reaches the tunnel exit node, the payload packet is decapsulated, and routed in a normal manner. This effectively creates an overlay network over the existing routing infrastructure.
Moreover, the payload packet may be encrypted so that intermediate routers cannot see the contents of the inner packet. Since the tunneling hides the source and destination addresses of the inner packet, the existing routing infrastructure can only make a routing decision on the basis of the outer packet.
However, this may lead to a phenomenon known as a tunneling loop when a tunnel packet is routed back to the tunnel entry node before reaching the tunnel exit node.
Still moreover, the tunneling loop is more likely to occur if a packet needs to undergo several levels of encapsulation. Since the encapsulation conceals the source address of the inner packet, a tunnel entry node may not recognize that it has already tunneled this packet previously. The tunneling loop is not desirable because it quickly eats up network resources.
A packet in a tunneling loop (along a tunneling loop) gets routed infinitely because a new Hop Limit field is set in each encapsulated packet. In consequence, for safeguarding against routing loop, the existing mechanism using hop limit becomes ineffective.
Yet moreover, each encapsulation adds an extra packet header to the packet, which enlarges the packet size. The extreme enlargement of the packet size may cause fragmentation. To this end, a different packet (divided packet) is introduced into the tunneling loop.
There are many possible cases in which a tunneling loop might occur. FIGS. 1A and 1B show two possible scenarios.
In FIG. 1A, MR (Mobile Router) 110, MR 112 and MR 114 are roaming in the Internet 100. There is a possibility that each of these mobile routers forms a tunneling loop.
In this case, MR 110 is connected to MR 112 as shown by the connection 120, MR 112 is connected to MR 114 as shown by the connection 122, and MR 114 is connected to MR 110 as shown by the connection 124. Whenever one (for example, MR 110) of the mobile routers makes the tunneling to its HA (Home Agent) 140, MR 110 encapsulates the packet for the tunneling to HA 140 and hands over the packet to MR 112 forming an access router of MR 110.
MR 112 further encapsulates the packet to hand over the packet to its own home agent. The packet is passed to MR 114 for the encapsulation of the packet. This goes on forever, and each of the mobile routers continuously adds one layer of encapsulation to the packet.
FIG. 1B shows a scenario in which MN (Mobile Node) 130 has two home addresses (MN. HoA1 and MN. HoA2) and home agents (HA 140 and HA 142) respectively corresponding thereto exist.
HA 140 manages the home address MN. HoA1, while HA 142 manages the home address MN. HoA2. Let it be assumed that MN 130 accidentally or intentionally has notified to HA 140 that its own care-of address (CoA) is MN. HoA2 and has notified to HA 142 that its own care-of address (CoA) is MN. HoA1.
The outcome is that, in a binding cache 150 of HA 140, there is stored an entry having a home address (HoA) field 162 including MN. HoA1 and a care-of address (CoA) field 164 including MN. HoA2. Likewise, in a binding cache 152 of HA 142, there is stored an entry having a home address field 166 including MN. HoA2 and a care-of address field 168 including MN. HoA1.
Now, in a case in which one (for example, HA 140) of the home agents receives a packet addressed to MN 130, HA 140 encapsulates the packet so that the packet is transferred to the care-of address (i.e., MN. HoA2) specified in its own binding cache. This is shown as a path 172 in FIG. 1B.
HA 142 receives (intercepts) this packet and tunnels the packet to the care-of address (MN. HoA1) of MN 130 in its own binding cache 152. This causes the packet to be returned through the tunnel to HA 140 as shown as the path 174 in FIG. 1B. Moreover, this loop will go on indefinitely.
The following Non-Patent Document 1 discloses the prevention of catastrophic consequences of a tunneling loop by use of a Tunnel Encapsulation Limit (TEL) option. This TEL option is a destination header option containing the maximum number of encapsulations a packet can undergo.
Normally, an intermediate routing node would not inspect the destination header of a transit packet. However, the Non-Patent Document 1 requires that all tunnel entry nodes inspect the destination header of a packet before encapsulation. In addition, if a TEL option is found in the packet, the tunnel entry node must first check that the maximum number of encapsulations allowed in the TEL option is not zero.
In a case in which the value specified in the TEL option is zero, the tunnel entry node discards the packet and transmits to the packet originator an Internet Control Message Protocol (ICMP) error for notifying a problem to the originator.
Moreover, if the TEL option is not zero, the tunnel entry node conducts the packet encapsulation processing to add a TEL option, containing a value obtained by subtracting one from the original TEL option (TEL option at the reception of the packet), to a new tunnel packet header.
On the other hand, in a case in which the original packet (received packet) does not contain a TEL option, the tunnel entry node carries out the encapsulation processing and adds to the tunnel packet header a TEL option containing a default numeric value of the maximum encapsulation. This default numeric value is a parameter set by the tunnel entry node.
Furthermore, FIG. 1C shows an example of an operation of a technique disclosed in the aforesaid Non-Patent Document 1. Here, a source node 180 (expressed as source in FIG. 1C) is a data transmitting node which transmits data packets to an arbitrary destination. The packets go through a path by way of three tunnel entry points (TEP 182, TEP 184, TEP 186). Let it be assumed that the three tunnel entry points, however, form a tunneling loop due to mis-configuration or for other reasons.
When the source node 180 transmits a data packet 187 (expressed as Data in FIG. 1C), the data packet 187 reaches the first tunnel entry (TEP 182). TEP 182 encapsulates the data packet into a tunnel packet 188 and adds a TEL option to the tunnel packet header. Since the payload packet 187 does not contain any TEL option, the TEL option in the tunnel packet 188 has a limit field in which set is a default value (for example, “4”).
Moreover, TEP 184 tunnels this packet (in FIG. 1C, expressed as Pkt {TEL=3}) to TEP 186, thereby generating a packet 189 with a TEL limit of “3” (in FIG. 1C, expressed as Pkt {TEL=3}). TEP 186 further tunnels this packet to TEP 182, thereby generating a packet 190 with a TEL limit of “2” (in FIG. 1C, expressed as Pkt {TEL=2}). TEP 184 still further tunnels this packet to TEP 184, thereby generating a packet 191 with a TEL limit of “1” (in FIG. 1C, expressed as Pkt {TEL=1}). Finally, TEP 184 tunnels this packet to TEP 186, which produces a packet 192 with a TEL limit of “0” (in FIG. 1C, expressed as Pkt {TEL=0}).
At this time, TEP 186 notices that the received packet has a TEL option with a value of zero. So further implementation of encapsulation becomes impossible. TEP 186 then discards the packet 192 and sends back to the source (i.e., TEP 184) of the packet 192 an ICMP error message 193 (in FIG. 1C, expressed as ICMP-Error) indicative of the original TEL option of the packet 192.
Upon receipt of this ICMP error message 193, TEP 184 extracts the original packet 191 from the ICMP error message 193 and sends back to the source of the packet 191 (i.e., TEP 182) an ICMP error message 194 (in FIG. 1C, expressed as ICMP-Error) indicative of the TEL option of the packet 191. This return of the ICMP error message is carried out until the packet extracted from the received ICMP error message contains no TEL option (that is, the ICMP error messages 195 to 197 (in FIG. 1C, expressed as ICMP-Error) are returned sequentially). In this connection, in FIG. 1C, when TEP 182 receives the ICMP error message 197, the packet contains no TEL option. Following this, a final ICMP error message 198 (in FIG. 1C, expressed as ICMP-Error) is sent from TEP 182 to the original source node 180.
In addition, there exists another conventional technique which tries to solve the problems related to the routing loop. For example, the following Patent Document 1 discloses a method of making an estimation as to whether or not a routing loop has occurred for detecting a common routing loop by using a counter for counting the number of packets for a predetermined period of time for each hop number included in their IP headers.
Still additionally, there is a different conventional technique which tries to prevent a routing loop itself. For example, the following Patent Document 2 discloses a mobile ad-hoc routing method which tries to prevent a routing loop. Yet additionally, the following Patent Document 3 discloses a routing method of using a spanning tree algorithm (global tree algorithm) for preventing the occurrence of a routing loop with respect to layer 2 tunneling protocol (L2TP) and virtual private network (VPN).    Non-Patent Document 1: “Generic Packet Tunneling in IPv6 Specification”, RFC2473, December 1998    Patent Document 1: US Patent Application Publication    Patent Document 2: US Patent Application Publication 2004/0146007    Patent Document 3: U.S. Pat. No. 6,765,881
However, although the technique disclosed in the Non-Patent Document 1 can prevent tunnel loop to continuously develop infinitely by the employment of the above-mentioned TEL options, it is an insufficient solving method with respect to complicated problems. In particular, in the case of the employment of the TEL options, a receiver, who receives ICMP error messages, cannot make a decision as to whether the reason that the TEL value is zero is because of a tunneling loop or because of the mere insufficient setting of TEL with respect to the number of tunnels through which the packet is required to pass until reaching a final destination.
Therefore, it is unclear how the tunnel entry node handles ICMP error notifying the arrival at the limit of tunnel encapsulation.
The tunnel entry node can increase the default TEL value to try the passing of packets. However, in a case in which a tunneling loop actually exists, the reception of ICMP error and the increase of the default TEL value may endlessly take place.
Moreover, the tunnel entry node can merely reject a tunnel packet having the same destination address on the assumption that a tunnel loop exists. However, if the real reason for the occurrence of an ICMP error is that the number of tunnels through which the packet is required to pass is larger than the TEL value set in order for the packet to reach the final destination, unnecessary service rejection can take place.
From the above explanation, it is seen that the problem related to the use of the TEL option arises because the TEL option does not include information whereby the tunnel entry node can distinguish between a case of the formation of a tunnel loop and a case of the number of tunnels through which the packet is required to pass being larger than the set default TEL value.
In addition, the method disclosed in Patent Document 1 is not suitable for a router made to handle thousands of packets per second. Still additionally, it is more like a heuristic method of estimating an indication of a routing loop than an actual loop detection algorithm.
The methods disclosed in Patent Documents 2 and 3 create a problem in that the calculation cost for deliberately preventing loop may not be justifiable, particularly when the probability of the loop occurrence is considerably low. The tunneling protocol makes use of the underlying routing infrastructure with respect to the packet routing from the tunnel entry node to the tunnel exit node. Therefore, the above-mentioned problem applies particularly to the tunneling protocol. Moreover, as long as the underlying routing infrastructure does not have any routing loop, the actual possibilities of the occurrence of a tunneling loop are considerably low. For this reason, a complete and complicated loop avoidance mechanism is not suitable for tunneling protocols.